As we know, some global optimization problems cannot be solved using analyticmethods, so numeric/algorithmic approaches are used to find near to the optimalsolutions for them. A stochastic global optimization algorithm (SGoal) is aniterative algorithm that generates a new population (a set of candidatesolutions) from a previous population using stochastic operations. Althoughsome research works have formalized SGoals using Markov kernels, suchformalization is not general and sometimes is blurred. In this paper, wepropose a comprehensive and systematic formal approach for studying SGoals.First, we present the required theory of probability (\sigma-algebras,measurable functions, kernel, markov chain, products, convergence and so on)and prove that some algorithmic functions like swapping and projection can berepresented by kernels. Then, we introduce the notion of join-kernel as a wayof characterizing the combination of stochastic methods. Next, we define theoptimization space, a formal structure (a set with a \sigma-algebra thatcontains strict \epsilon-optimal states) for studying SGoals, and we developkernels, like sort and permutation, on such structure. Finally, we present somepopular SGoals in terms of the developed theory, we introduce sufficientconditions for convergence of a SGoal, and we prove convergence of some popularSGoals.
展开▼
